class Solution {
public:
    bool r_number[10][10] = { false };
    bool c_number[10][10] = { false };
    bool s_number[3][3][10] = { false };
    bool have_ans = false;
    void dfs(vector<vector<char>>& board, int row, int col)
    {
        if(row == board.size() && col == 0)
        {
            have_ans = true;
            return;
        }
        if(have_ans) return;
        char& ch = board[row][col];
        if(ch == '.')
        {
            for(int x = 1; x <= 9; ++x)
                if(!r_number[row][x] && !c_number[col][x] && !s_number[row/3][col/3][x])
                {
                    board[row][col] = x + '0';
                    s_number[row/3][col/3][x] = c_number[col][x] = r_number[row][x] = true;
                    if(col == 8) dfs(board, row + 1, 0);
                    else dfs(board, row, col + 1);
                    if(have_ans) return;
                    s_number[row/3][col/3][x] = c_number[col][x] = r_number[row][x] = false;
                    board[row][col] = '.';
                }
        }
        else
        {
            if(col == 8) dfs(board, row + 1, 0);
            else dfs(board, row, col + 1);
        }
    }
    void solveSudoku(vector<vector<char>>& board) 
    {
        for(int row = 0; row < board.size(); ++row)
            for(int col = 0; col < board[row].size(); ++col)
                if(board[row][col] != '.')
                {
                    int x = board[row][col] - '0';
                    s_number[row/3][col/3][x] = c_number[col][x] = r_number[row][x] = true;
                }
        dfs(board, 0, 0);
    }
};